import java.util.Stack;

/**
 * 901. 股票价格跨度
 * https://leetcode-cn.com/problems/online-stock-span/
 */
public class Solutions_901 {
    public static void main(String[] args) {
        StockSpanner obj = new StockSpanner();
        int res1 = obj.next(100);  // output: 1
        int res2 = obj.next(80);  // output: 1
        int res3 = obj.next(60);  // output: 1
        int res4 = obj.next(70);  // output: 2
        int res5 = obj.next(60);  // output: 1
        int res6 = obj.next(75);  // output: 4
        int res7 = obj.next(85);  // output: 6
        System.out.println("");
    }
}

/**
 * 解法二：单调栈优化——数组形式（30ms）
 */
class StockSpanner {
    // stack 保存 price
    int[] stack = null;
    // help 保存 price 对应的价格跨度数量
    int[] help = null;
    int idx = 0;

    public StockSpanner() {
        stack = new int[10001];
        help = new int[10001];
        idx = 0;
    }

    public int next(int price) {
        int res = 1;
        while (idx > 0 && stack[idx - 1] <= price) {
            // 比 price 小的，都弹出
            // 关键：次数需要累加
            res += help[--idx];
        }
        // 最终 price 与价格跨度数量保存到 stack 和 help 中
        stack[idx] = price;
        help[idx] = res;
        idx ++;
        return res;
    }
}

/**
 * 解法一：单调栈形式（39ms）
 */
class StockSpanner2 {
    // stack 保存 price
    Stack<Integer> stack = null;
    // help 保存 price 对应的价格跨度数量
    Stack<Integer> help = null;

    public StockSpanner2() {
        stack = new Stack<>();
        help = new Stack<>();
    }

    public int next(int price) {
        int res = 1;
        while (!stack.isEmpty() && stack.peek() <= price) {
            // 比 price 小的，都弹出
            stack.pop();
            // 关键：次数需要累加
            res += help.pop();
        }
        // 最终 price 与价格跨度数量保存到 stack 和 help 中
        stack.push(price);
        help.push(res);
        return res;
    }
}
